import ComparableObj from "../core/ComparableObj";
import Obj from "../core/Obj";
import Collection from "../core/Collection";
import IllegalArgumentException from "../exceptions/IllegalArgumentException";
import FullCapacityException from "../exceptions/FullCapacityException";
import Tree, {IterationDirection, Node} from "./Tree";
import {compareTo} from "../utils/Comparator";
import ArrayList from "../list/ArrayList";

const className = "binaryTree";

export default class BinaryTree<E extends ComparableObj<E>> extends Obj implements Tree<E> {

  protected root: Node<E> | undefined;
  private _size: number;
  private _capacity: number;

  public constructor(capacity: number = -1) {
    super();

    if (capacity < -1) {
      throw new IllegalArgumentException("capacity should be bigger than -1");
    }

    this.root = undefined;
    this._size = 0;
    this._capacity = capacity;
  }

  public add(e: E): E | undefined {
    if (this.full()) {
      throw new FullCapacityException(className, this._capacity);
    } else {
      if (this.root === undefined) {
        this.root = new Node(e);
        this._size ++;
        return undefined;
      } else {
        return this.addNode(this.root, e);
      }
    }

  }

  public capacity(): number {
    return this._capacity;
  }

  public clear() {
    this.root = undefined;
    this._size = 0;
  }

  public collect(iterationDirection: IterationDirection, collection: Collection<E>): void {
    if (this.root !== undefined) {
      switch (iterationDirection) {
        case IterationDirection.CENTRE:
          this.centreIter(this.root, collection);
          break;
        case IterationDirection.LEFT:
          this.leftIter(this.root, collection);
          break;
        case IterationDirection.RIGHT:
        default:
          this.rightIter(this.root, collection);
      }
    }
  }

  public contains(e: E): boolean {
    return this.getNode(this.root, e) !== undefined;
  }

  public equals(b: Obj): boolean {
    if (b instanceof BinaryTree) {
      const aArrayList = new ArrayList<E>();
      this.collect(IterationDirection.CENTRE, aArrayList);
      const bArrayList = new ArrayList<any>();
      b.collect(IterationDirection.CENTRE, bArrayList);
      return aArrayList.equals(bArrayList);
    }
    return false;
  }

  public hashCode(): number {
    const aArrayList = new ArrayList<E>();
    this.collect(IterationDirection.CENTRE, aArrayList);
    return aArrayList.hashCode();
  }

  public get(e: E): E | undefined {
    const node = this.getNode(this.root, e);
    return node === undefined ? undefined : node.key;
  }

  public grow(capacity: number): boolean {
    if (capacity < this._capacity && capacity !== -1) {
      throw new IllegalArgumentException(
        "capacity " + capacity + " is smaller than current capacity " + this._capacity + " and is not -1");
    } else {
      this._capacity = capacity;
      return true;
    }
  }

  public isEmpty(): boolean {
    return this._size == 0;
  }

  public isFull(): boolean {
    return this._size === this._capacity;
  }

  public max(): E | undefined {
    return this.root === undefined ? undefined : this.maxNode(this.root).key;
  }

  public min(): E | undefined {
    return this.root === undefined ? undefined : this.minNode(this.root).key;
  }

  public remove(e: E): E | undefined {
    const removedNode = this.removeNode(this.root, e);
    return removedNode === undefined ? undefined : removedNode.key;
  }

  public size(): number {
    return this._size;
  }

  private addNode(node: Node<E>, e: E): E | undefined {
    if (compareTo(e, node.key) === -1) {
      if (node.getLeft() === undefined) {
        node.setLeft(new Node(e));
        this._size++;
        return undefined;
      } else {
        return this.addNode(node.getLeft() as Node<E>, e);
      }
    } else if (compareTo(e, node.key) === 1) {
      if (node.getRight() === undefined) {
        node.setRight(new Node(e));
        this._size++;
        return undefined;
      } else {
        return this.addNode(node.getRight() as Node<E>, e);
      }
    } else {
      let oldValue = node.key;
      node.key = e;
      return oldValue;
    }
  }

  private getNode(node: Node<E> | undefined, key: E): Node<E> | undefined {
    if (node === undefined) {
      return undefined;
    }
    if (compareTo(key, node.key) === -1) {
      return this.getNode(node.getLeft(), key);
    } else if (compareTo(key, node.key) === 1) {
      return this.getNode(node.getRight(), key);
    } else {
      return node;
    }
  }

  private removeNode(node: Node<E> | undefined, e: E): Node<E> | undefined {
    if (node === undefined) {
      return undefined;
    }

    if (compareTo(e, node.key) === -1) {
      node.setLeft(this.removeNode(node.getLeft(), e));
      return node;
    } else if (compareTo(e, node.key) === 1) {
      node.setRight(this.removeNode(node.getRight(), e));
      return node;
    } else {
      if (node.getLeft() == undefined && node.getRight() === undefined) {
        node = undefined;
        return node;
      }

      if (node.getLeft() === undefined) {
        node = node.getRight();
        return node;
      } else if (node.getRight() === undefined) {
        node = node.getLeft();
        return node;
      }

      const aux = this.minNode(node.getRight() as Node<E>);
      node.key = aux.key;
      node.setRight(this.removeNode(node.getRight(), aux.key));
      this._size--;
      return node;
    }
  }

  private minNode(node: Node<E>): Node<E> {
    let current = node;
    while (current != undefined && current.getLeft() != undefined) {
      current = current.getLeft() as Node<E>;
    }
    return current;
  }

  private maxNode(node: Node<E>) {
    let current = node;
    while (current !== undefined && current.getRight() !== undefined) {
      current = current.getRight() as Node<E>;
    }
    return current;
  }

  protected full(): boolean {
    return this._size === this._capacity;
  }

  private leftIter(node: Node<E> | undefined, collection: Collection<E>) {
    if (node !== undefined) {
      this.leftIter(node.getLeft(), collection);
      collection.add(node.key);
      this.leftIter(node.getRight(), collection);
    }
  }

  private centreIter(node: Node<E> | undefined, collection: Collection<E>) {
    if (node !== undefined) {
      collection.add(node.key);
      this.centreIter(node.getLeft(), collection);
      this.centreIter(node.getRight(), collection);
    }
  }

  private rightIter(node: Node<E> | undefined, collection: Collection<E>) {
    if (node !== undefined) {
      this.rightIter(node.getLeft(), collection);
      this.rightIter(node.getRight(), collection);
      collection.add(node.key);
    }
  }
}
